package chapter04_RecursionAndDynamic;

/**
 * 描述：
 *      汉诺塔：给定一个整数n,代表汉诺塔游戏中从小到大放置的n个圆盘，假设开始时所有的圆
 * 盘都放在左边的柱子上，想按照汉诺塔游戏的要求把所有的圆盘都移到右边的柱子上。实
 * 现函数打印最优移动轨迹。
 *      进阶：给定一个整型数组arr,其中只含有1、2和3,代表所有圆盘目前的状态，1代表左柱，
 * 2代表中柱，3代表右柱，arr[i]的值代表第i+1 个圆盘的位置。比如，arr=[3,3,2,1], 代表第
 * 1个圆盘在右柱上、第2个圆盘在右柱上、第3个圆盘在中柱上、第4个圆盘在左柱上。
 * 如果arr代表的状态是最优移动轨迹过程中出现的状态，返回arr这种状态是最优移动轨迹
 * 中的第几个状态。如果arr代表的状态不是最优移动轨迹过程中出现的状态，则返回-1。
 * @author hl
 * @date 2021/6/8 10:51
 */
public class Hanoi {
    public static void main(String[] args) {
        hanoi(3);
        int[] arr = {3,3};
        int i = step1(arr);
        int i2 = step2(arr);
        System.out.println(i);
        System.out.println(i2);
    }

    /**
     * 假设将左边柱子上的圆盘从上到下编号1~i，那么最优的路径为：
     * 1）将1~i-i的圆盘移动的到中间柱子上
     * 2）将圆盘i移动到目标圆盘上
     * 3）将圆盘1~i-1的圆盘移动到目标圆盘上
     * 左柱、右柱、中柱在每一个递归过程中都是不一样的。
     * @param n
     */
    public static void hanoi(int n){
        if (n < 1) {
            return ;
        }
        func(n, "left", "right", "mid");
    }

    private static void func(int n, String from, String to, String mid) {
        if (n <= 1) {
            System.out.println("move from " + from + " to " + to);
            return ;
        }
        func(n - 1, from, mid, to);
        func(1, from, to, mid);
        func(n - 1, mid, to, from);
    }

    /**
     * 首先求都在from柱上的圆盘1~i，如果都移动到to上需要的最少步数，假设为S(i)。那么根据上面的步骤
     * S(i) = S(i - 1) + 1 + S(i - 1) ==> S(i) + 1 = 2(S(i - 1) + 1), S(1) + 1 = 2 ==> S(i) = 2^i - 1
     * 判断每个圆盘的状态有
     * @param arr
     * @return  返回当前状态在最优状态的第几部
     */
    public static int step1(int[] arr){
        if (arr == null || arr.length == 0) {
            return -1;
        }
        return process(arr, arr.length - 1, 1, 2, 3);
    }

    private static int process(int[] arr, int i, int from, int mid, int to) {
        if (i == -1) {
            return 0;
        }
        if (arr[i] != from && arr[i] != to) {
            return -1;
        }
        if (arr[i] == from) {
            return process(arr, i - 1, from, to, mid);
        }else{
            //此时至少经过了2^(i-1)步
            int res = process(arr, i - 1, mid, from, to);
            if (res == -1) {
                return -1;
            }
            return (1 << i) + res;
        }
    }

    public static int step2(int[] arr){
        if (arr == null || arr.length == 0) {
            return -1;
        }
        int from = 1;
        int mid = 2;
        int to = 3;
        int res = 0;
        int tmp = 0;
        int i = arr.length - 1;
        while(i >= 0){
            if (arr[i] != from && arr[i] != to) {
               return -1;
            }
            if (arr[i] == to) {
                res += 1 << i;
                tmp = from;
                from = mid;
            }else{
                tmp = to;
                to = mid;
            }
            mid = tmp;
            i--;
        }
        return res;
    }
}
